package myself.a014Recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 叶之越
 * Description
 * Date 2021/2/2
 * Time 14:11
 * Mail 739153436@qq.com
 */
public class PrintAllPermutations {
    public static List<String> permutation1(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        ArrayList<Character> rest = new ArrayList();
        for (char cha : str) {
            rest.add(cha);
        }
        String path = "";
        f(rest, path, ans);
        return ans;
    }

    // 打印一个字符串的全部排列，初级版本
    private static void f(ArrayList<Character> rest, String path, List<String> ans) {
        if (rest.isEmpty()) {
            ans.add(path);
        } else {
            for (int i = 0; i < rest.size(); i++) {
                Character cur = rest.remove(i);
                f(rest, path + cur, ans);
                rest.add(i, cur);
            }
        }
    }

    // 打印一个字符串的全部排列，优化版本
    public static void g1(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(str));
        } else {
            for (int i = index; i < str.length; i++) {
                swap(str, index, i);
                g3(str, index, ans);
                swap(str, index, i);
            }
        }
    }


    // 打印一个字符串的全部排列并且去重，优化版本，没有使用HashSet
    // ![](http://img.yhzcmxq.cn/picgo/20210202154034.png)
    public static void g3(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(str));
        } else {
            boolean[] visited = new boolean[256];
            for (int i = index; i < str.length; i++) {
                if (!visited[str[i]]) {
                    visited[str[i]] = true;
                    swap(str, index, i);
                    g3(str, index, ans);
                    swap(str, index, i);
                }
            }
        }
    }

    private static void swap(char[] str, int a, int b) {
        char temp = str[a];
        str[a] = str[b];
        str[b] = temp;
    }
}
